package mo.tags.greedy;

import java.util.ArrayDeque;
import java.util.Arrays;

public class L670 {

    public int maximumSwap(int num) {
        if (num <= 10) {
            return num;
        }
        String s = String.valueOf(num);
        int n = s.length();
        int[][] pairs = new int[n][];
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            pairs[i] = new int[]{chars[i]-'0', i};
        }
        Arrays.sort(pairs, (p1, p2) -> {
            if (p1[0] != p2[0]) {
                return p2[0] - p1[0];
            }
            return p2[1] - p1[1];
        });

        for (int i = 0; i < n; i++) {
            if (chars[i] - '0' != pairs[i][0]) {
                int pos = pairs[i][1];
                for (int j = 0; j < i; j++) {
                    if (pairs[j][0] == pairs[i][0]) {
                        pos = pairs[j][1];
                        break;
                    }
                }
                char tmp = chars[i];
                chars[i] = Character.forDigit(pairs[i][0], 10);
                chars[pos] = tmp;
                break;
            }
        }

        return Integer.parseInt(String.valueOf(chars));
    }

    public static void main(String[] args) {
        L670 test = new L670();
        System.out.println(test.maximumSwap(756776));
    }

}
